\documentclass{beamer}
\usepackage{graphicx}
\usetheme{CambridgeUS}
\usecolortheme{seahorse}

\mode<presentation>

\title[Case study in Geometric Algebra]{A case study in geometric algebra: \\ fitting a 3D point cloud to room models}
\author[Hueting]{Moos Hueting \\ \small Supervised by Marcel Worring and Dani\"el Fontijne}
\institute{University of Amsterdam}
\date[23-06-2011]{June 23, 2011}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{Linear algebra vs. Geometric Algebra}
  \begin{columns}[l]
  \column{0.45\textwidth}
  \emph{Linear Algebra}
  \begin{itemize}
    \item Numbers and matrices represent everything
    \item Two products (matrix product and dot product)
    \item Representing geometric objects is thus contrived
    \item Never coordinate free
  \end{itemize}
  \column{0.45\textwidth}
  \emph{Geometric Algebra}
  \begin{itemize}
    \item Geometric objects as elements of computation
    \item Coordinatefree
    \item Many products, but all subsumed by one general product
    \begin{itemize}
      \item Wedge ($\wedge$) product and contraction ($\rfloor$)
      \item Subsumed by geometric product, written as a space
    \end{itemize}
    \item Compact code
  \end{itemize}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Geometric Algebra - an example}
  \begin{columns}[l]
    \column{0.4\textwidth}
    \begin{figure}[ht]
    \centering
    \includegraphics[width=\textwidth]{img/3points}
    \caption{Points $a, b, c$}
    \end{figure}
    \column{0.4\textwidth}
    \begin{figure}
    \centering
    \includegraphics[width=\textwidth]{img/3pointscircle}
    \caption{$a \wedge b \wedge c$}
    \end{figure}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Geometric Algebra - an example continued}
  \begin{itemize}
    \item The generated circle is now a basic element of the algebra
      \begin{itemize}
        \item Original points not involved anymore!
      \end{itemize}
    \item The circle can then be used in numerous applications
    \begin{itemize}
      \item Check if other point is on circle
      \item Plane through circle (in higher dimensional space)
      \item Find center
    \end{itemize}
    \item Doing the same in linear algebra is quite involved
    \begin{enumerate}
      \item Calculate the center and radius first
      \item Circle \emph{represented} by numbers, not a basic object
    \end{enumerate}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Case study}
  \begin{itemize}
    \item The advantages sound nice theoretically, but what about practice?
    \item Fitting a point cloud generated from pictures of a room to a 3D room model
    \item Has been done often with classical techniques
    \begin{itemize}
      \item RANSAC
      \item Hough transform
    \end{itemize}
    \item Never with geometric algebra
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Two datasets}
  \begin{columns}[l]
  \column{0.45\textwidth}
  \begin{figure}
  \centering
  \caption{Front and side view}
  \includegraphics[width=0.4\textwidth]{img/trivial1}
  \hspace{0.4cm}
  \includegraphics[width=0.4\textwidth]{img/trivial2}
  \caption{Generated from artificial model}
  \end{figure}
  \column{0.45\textwidth}
  \begin{figure}
  \centering
  \caption{Front and side view}
  \includegraphics[width=0.4\textwidth]{img/nedsense1}
  \hspace{0.4cm}
  \includegraphics[width=0.4\textwidth]{img/nedsense2}
  \caption{Generated using stereovision, front and side view}
  \end{figure}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{RANSAC}
  \begin{columns}[l]
  \column{0.4\textwidth}
  \begin{itemize}
    \item Pick N points at random
    \item Create model
    \item Check fit of model
    \item Improve model
    \item Return best model found
  \end{itemize}
  \column{0.4\textwidth}
  \begin{figure}
  \centering
  \includegraphics[width=\textwidth]{img/ransacline}
  \caption{2D ransac}
  \end{figure}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{GA vs. LA}
  \begin{columns}[l]
  \column{0.45\textwidth}
  \emph{Linear Algebra}
  \begin{enumerate}
    \item Solve system of equations $ax_i + by_i + cy_i + d = 0$ for $i \in {0-3}$
    \item Gives equation $ax + by + cy + d = 0$ as representation of plane
    \item Distance between point $p$ and plane is $\frac{|ap_x + bp_y + cp_z + d|}{\sqrt{a^2} + \sqrt{b^2} + :\sqrt{c^2}}$
  \end{enumerate}
  \column{0.45\textwidth}
  \emph{Geometric Algebra}
  \begin{itemize}
    \item Plane $P$ is defined by $p_1 \wedge p_2 \wedge p_3 \wedge \infty$
    \item Distance between point $p$ and plane $P$ is $p \rfloor P^*$
    \item This is fully algebraic!
  \end{itemize}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Hough transform}
  \begin{figure}
  \includegraphics[width=0.7\textwidth]{img/houghdiagram}
  \caption{Hough transform in 2D}
  \end{figure}
\end{frame}

\begin{frame}
  \frametitle{GA vs. LA}
  \begin{columns}[l]
  \column{0.45\textwidth}
  \emph{Linear Algebra}
  \begin{enumerate}
    \item Solve system of equations $ax_i + by_i + cy_i + d = 0$ for $i \in {0-3}$
    \item Gives equation $ax + by + cy + d = 0$ as representation of plane
    \item This representation is not unique, so convert this representation to Hesse Normal Form (too involved to list here)
    \item Increase accumulator cell corresponding to this representation
  \end{enumerate}
  \column{0.45\textwidth}
  \emph{Geometric Algebra}
  \begin{itemize}
    \item Plane $P$ is defined by $p_1 \wedge p_2 \wedge p_3 \wedge \infty$
    \item Normalize plane by dividing by norm
    \item Increase accumulator cell corresponding to this representation
    \item Again, fully algebraic
  \end{itemize}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{RANSAC results}
  \begin{columns}[l]
  \column{0.45\textwidth}
  \begin{figure}
  \centering
  \includegraphics[width=\textwidth]{img/ransactrivial}
  \caption{RANSAC on artificial set}
  \end{figure}
  \column{0.45\textwidth}
  \begin{figure}
  \centering
  \includegraphics[width=\textwidth]{img/ransacnedsense}
  \caption{RANSAC on stereovision set}
  \end{figure}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Hough results}
  \begin{columns}[l]
  \column{0.45\textwidth}
  \begin{figure}
  \centering
  \includegraphics[width=\textwidth]{img/houghtrivial}
  \caption{HT on artificial set}
  \end{figure}
  \column{0.45\textwidth}
  \begin{figure}
  \centering
  \includegraphics[width=\textwidth]{img/houghnedsense}
  \caption{HT on stereovision set}
  \end{figure}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Conclusion for now and what's next}
  \begin{itemize}
    \item Classical methods such as Hough and RANSAC can be transformed to GA
    \item Expression more compact
    \item Methods used not optimal for room fitting (yet)
  \end{itemize}
  \begin{itemize}
    \item 3D to 2D, Hough transform
    \begin{itemize}
      \item Really shows the power of Geometric Algebra
      \begin{itemize}
        \item Rotate entire point cloud so that floor is level with horizontal axis
        \item Looking from above, the problem is now 2D
        \item Rotating a plane to another one is very contrived in LA, very easy in GA
      \end{itemize}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \begin{center}
  \huge Questions?
  \end{center}
\end{frame}

\end{document}
